MAX = 0
d = {}

p = [1 for i in xrange(1000000)]
p[0] = p[1] = 0
for i in xrange(2, 1000000):
    if p[i]:
        for j in xrange(i + i, 1000000, i):
            p[j] = 0

ps = [i for i in xrange(1000000) if p[i]]

print p[:12]


N = 1000000

for m in xrange(1, N):
    good = 1
    for i in xrange(1, m):
        if pow(i, m + 4, m) != i:
            if i not in d:
                d[i] = 1
                print 'i: %d' % i
            good = 0
            break
        if i > 100:
            break
    if good:
        print m
        n = m
        for prime in ps:
            while n % prime == 0:
                print prime,
                n /= prime
            if p[n]:
                print n
                break
            if n == 1:
                print ''
                break


